package leetcode_300;

/**
 *@author 周杨
 *HouseRobberII_213 环形抢劫 要么第一个不枪 要么最后一个不抢  所以把第一个和最后一个分别去掉一次    用动态规划
 *describe:AC 100%
 *2018年6月14日 下午7:43:09
 */
public class HouseRobberII_213 {
	int[] nums;
	public static void main(String[] args) {
		HouseRobberII_213 test=new HouseRobberII_213();
		//System.out.println(test.rob(new int[] {2,7,9,3,1}));
		System.out.println(test.rob(new int[] {1,3,1,3,100}));
	}
	public int rob(int[] nums) {
		this.nums=nums;
		if(nums.length==0)
			return 0;
        if(nums.length==1)
        	return nums[0];
        if(nums.length==2)
        	return Math.max(nums[0], nums[1]);
        if(nums.length==3) {
        	return Math.max(Math.max(nums[0], nums[1]), nums[2]);
        }
        return Math.max(help(0,nums.length-1), help(1,nums.length));
        
    }
	
	public int help(int start,int end) {
		if(end-start==0)
			return 0;
        if(end-start==1)
        	return nums[start];
        if(end-start==2)
        	return Math.max(nums[start], nums[start+1]);
        int pre=nums[start],after=nums[start+1];
        for(int i=start+2;i<end;++i) {
        	int now=Math.max(pre+nums[i], after+nums[i]-nums[i-1]);
        	int temp=pre;
        	pre=after;
        	after=now;
        }
        return Math.max(pre,after);
	}
	
	 /**
	 * describe:没有多余的判断 而且不必减前一个
	 * 2018年6月14日 下午8:30:03
	 */
	public int rob1(int[] nums) {
	        if (nums == null || nums.length == 0)
	            return 0;
	        if (nums.length == 1)
	            return nums[0];
	        
	        return Math.max(robBasic(nums, 0, nums.length - 2), robBasic(nums, 1, nums.length - 1));
	    }
	                        
	    private int robBasic(int[] nums, int start, int end) {
	        int preMax = 0;
	        int currMax = 0;
	        
	        for (int i = start; i <= end; i++) {
	            int temp = currMax;
	            currMax = Math.max(currMax, preMax + nums[i]);
	            preMax = temp;
	        }
	        return currMax;
	    }
}
